|
課程名稱 |
組合學二
Combinatorics (Ⅱ) |
|
開課學期 |
111-2 |
|
授課對象 |
理學院 數學研究所 |
|
授課教師 |
戴尚年 |
|
課號 |
MATH7702 |
|
課程識別碼 |
221EU3300 |
|
班次 |
|
|
學分 |
3.0 |
|
全/半年 |
半年 |
|
必/選修 |
選修 |
|
上課時間 |
星期二5(12:20~13:10)星期五8,9(15:30~17:20) |
|
上課地點 |
天數101天數101 |
|
備註 |
本課程以英語授課。
總人數上限：40人 |
|
|
|
|
課程簡介影片 |
|
|
核心能力關聯 |
核心能力與課程規劃關聯圖 |
|
課程大綱
|
|
為確保您我的權利,請尊重智慧財產權及不得非法影印
|
|
課程概述 |
In this course, we will study the use of algorithms in combinatorics. We will begin by
analysing some important algorithms on graphs, introducing the basics of complexity
theory in the process. The main part of the course, though, will concern the use of
algorithmic thinking to prove theoretical results. For example, we will see how one can
use network flows and the Ford-Fulkerson algorithm to prove results about graph
connectivity, or how linear programming can be applied to several problems in the
field. Finally, we will discuss probabilistic algorithms, and to what extent they can be
derandomized for applications. |
|
課程目標 |
• Cover important graph algorithms for spanning trees, matchings, and more
• Use algorithms to prove theoretical results about connectivity, colouring, etc.
• Learn how to analyse randomized algorithms, and how to make them
deterministic |
|
課程要求 |
Successful completion of Combinatorics I or Graph Theory I, or an equivalent course
Knowledge of linear algebra, calculus and probability |
|
預期每週課後學習時數 |
|
|
Office Hours |
|
|
指定閱讀 |
|
|
參考書目 |
• Lovász, Pelikán and Vesztergombi, Discrete Mathematics
• Matoušek and Gärtner, Understanding and Using Linear Programming
• Hefetz, Krivelevich, Stojaković and Szabó, Positional Games |
|
評量方式
(僅供參考) |
|
|